//
// Created by Administrator on 2021/4/13.
//

/*给定一个 N 叉树，返回其节点值的 前序遍历 。

N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

进阶：

递归法很简单，你可以使用迭代法完成此题吗?

示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]

示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/


#include <utility>
#include <vector>
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val = 0;
    vector<Node *> children;

    Node() = default;

    explicit Node(int _val) : val(_val) {};

    Node(int _val, vector<Node *> _children) {
        val = _val;
        children = std::move(_children);
    }
};

class Solution {  // 递归
public:
    vector<int> preorder(Node *root) {
        vector<int> vec;
        if (!root) return vec;
        dfs(root, vec);
        return vec;
    }

    void dfs(Node *root, vector<int> &v) {
        if (!root) return;
        v.push_back(root->val);
        for (auto &x:root->children) {
            dfs(x, v);
        }
    }

    vector<int> preorderRecursive(Node *root) {
        vector<int> vec;
        if (!root) return vec;
        stack<Node *> stk;
        stk.push(root);
        while (!stk.empty()) {
            Node *temp = stk.top();
            stk.pop();
            vec.push_back(temp->val);
            for (auto i = temp->children.rbegin(); i != temp->children.rend(); ++i) {
                // 倒序放入
                stk.push(*i);
            }
        }
        return vec;
    }
};

int main() {
    auto t6 = Node(6);
    auto t5 = Node(5);
    auto t4 = Node(4);
    auto t3 = Node(2);
    auto t2 = Node(3, vector<Node *>{&t5, &t6});
    auto t1 = Node(1, vector<Node *>{&t2, &t3, &t4});
    Solution sol;
//    vector<int> v = sol.preorderRecursive(&t1);
    vector<int> v = sol.preorder(&t1);
    for (const auto &x:v) cout << x;
    return 0;
}

